﻿#include <iostream>
using namespace std;
#include <string>

//字符串最后一个单词长度
//int main()
//{
//    string s1;
//    getline(cin, s1);
//    int end = s1.size();
//    int mark = s1.rfind(" ");
//    if (mark != s1.npos)
//    {
//        cout << end - mark - 1;
//    }
//    else 
//	  {
//        cout << s1.size();
//    }
//
//    return 0;
//}

//如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，
//短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
//字母和数字都属于字母数字字符。
//bool Isnum(char c)
//{
//    if ((c <= 'z' && c >= 'a') || (c <= 'Z' && c >= 'A') || (c <= '9' && c >= '0'))
//        return true;
//    else
//        return false;
//}
//
// bool isPalindrome(string s) {
//     string s1;
//     auto it = s.begin();
//     while (it != s.end())
//     {
//         if (Isnum(*it))
//                s1 += *it;
//            it++;
//     }
//     int i = 0;
//     int j = s1.size() - 1;
//        while (i <= j)
//        {
//            if (s1[i] == s1[j] || (s1[i] > '9') && abs(s1[i] - s1[j]) == 32)
//            {
//                i++;
//                j--;
//            }
//            else
//                return false;
//        }
//        return true;
//    }
//
//
// int main()
// {
//     string s = "0P";
//     cout << isPalindrome(s);
//     return 0;
// }

//给定一个字符串 s 和一个整数 k，从字符串开头算起，
// 每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
string reverseStr(string s, int k) {
    auto begin = s.begin();
    while (begin + 2 * k < s.end())
    {
        reverse(begin, begin + k);
        begin += 2 * k;
    }
    if (s.end() - begin < k)
    {
        reverse(begin, s.end());
    }
    else
    {
        reverse(begin, begin + k);
    }
    return s;
}

//给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，
// 同时仍保留空格和单词的初始顺序。
string reverseWords(string s) {
	auto begin = s.begin();
	while (begin < s.end())
	{
		int i = 0;
        while (*(begin + i) != ' ' && begin + i < s.end())
        {
            i++;
        }

		reverse(begin, begin + i);
		begin += (i + 1);
	}
	return s;
}
//给定两个以字符串形式表示的非负整数 num1 和 num2，
//返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式
// 
//思路：由于字符串表达的数字可能巨大，不能直接分别转换为整形，所以首先开辟一个数组，用来表示要求的数字的每一位
// 随后以一个数字num1的各个位的数字(从个位开始),轮流乘另一个数num2的各个位数，并把结果逐步储存到数组对应的位置
//此时数组表示的是没有进位的数字，随后进行进位，再从后向前走，找到第一个不为0的数据，加到数组上
string multiply(string num1, string num2) 
{
    string ret;
    if (num1[0] == '0' || num2[0] == '0')//处理任意一方数字为0的情况
        return (ret += '0');
    int* arr = new int[num1.size() + num2.size()] {0};
    //翻转字符串，方便于一个数字按照个位十位依次去拆分
    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());

    int i = 0;
    while (1)
    {
        if (i < num1.size())//i表示num1的个位，十位等等的依次各位
        {
            int mul = num1[i] - '0';//mul表示num1的某一位数字，用来乘另一个数字的各位数字
            int j = 0;
            while (j < num2.size())
            {
                arr[i + j] += mul * (num2[j] - '0');//i是两数字各位相乘，所得结果的起始存储位置
                j++;
                //而额外+j则可以表示十位百位等等依次增加时，需要额外补充的存储位置
            }
            i++;
        }
        else
            break;
    }
   
    //这里首先要进行进位，保证每一位的数字都是个位数
    for (int i = 0; i < num1.size() + num2.size() - 1; i++)
    {
        arr[i + 1] += arr[i] / 10;
        arr[i] = arr[i] % 10;
    }
    int j = num1.size() + num2.size() - 1;
    //数组的0到某一位置，表示的是逆序的数字结果，消除掉
    //要逆序访问并加到ret上，首先则要逆序寻找到不为0的第一个数字
    while (arr[j] == 0)
    {
        j--;
    }
    for (; j >= 0; j--)
    {
        ret += arr[j] + '0';
    }
    return ret;
}

int main()
{
    string s1 = "123";
    string s2 = "456";
    multiply(s1, s2);
    return 0;
}